from Row import Row
from common import *
from config import SBOXS
from generate_answer import get_monomials_literals, get_monomials_literals_alter

def init_matrix(width, sboxmat):
    """
        initialize a matrix
        width: how many bits the input will be
        sboxmat: ref to the sbox matrix
    """

    cols = get_cols_amount()

    # prepare the following vectors for the search equations procedure

    # [1, 1, ..., 1]
    # [0, 0, ..., 0] -
    # ...            |- (`rows` - 1) rows
    # [0, 0, ..., 0] -
    def build_zero_matrix(monomials_literals):
        m = []

        row0 = Row(monomials_literals[0], 0, size=cols, what_to_fill=1)
        m.append(row0)

        for i, monomial in enumerate(monomials_literals[1:]):
            m.append(Row(monomial, i + 1, size=cols))

        return m


    m = build_zero_matrix(get_monomials_literals(width))

    def init_sub_matrix(starting_row, col, cur, matrix):
        """
            init rows of input/output bits
            starting_row: where to start filling the rows
            col: the number of the column to fill in
            cur: the number to be filled with
            matrix: the matrix to operate with
        """
        def get_b_str(num):
            """
                fill 0 if the number of digits of the binary form of num is less than `width`
            """
            return ('{0:0%sb}' % width).format(num)

        for i in range(width):
            # for every digit in b_str, matrix[i][j] = int(digit)
            #   where i = starting_row + the position of the digit
            #         j = number of the column, i.e. col
            matrix[starting_row + i][col] = int(get_b_str(cur)[i])

    # initialize input/output bits by init_sub_matrix
    for i in range(cols):
        init_sub_matrix(1, i, i, m)
        init_sub_matrix(width + 1, i, sboxmat[i], m)

    def multiply_alter(matrix, i_of_xi):
        # TODO complete this part
        pass

    def multiply(matrix, i_of_xi):
        """
            generate the value of the monomials other than the input/output bits
            matrix: the matrix to operate with
            i_of_xi: the number of the xi, where xi is the input bit to multiply
        """
        for i in range(width):
            for j in range(cols):
                # for every j in [0..cols) matrix[k][j] = matrix[i_of_xi][j] * matrix[l][j]
                #   where, for i in (0..`width`),
                #               k = p1 + p2 + p3,
                #                   where p1 = 1 + 2 * width (the row of ones, the rows of the input/output bits
                #                         p2 = (i_of_xi - 1) * width (the number of rows of xk occupied, k < i_of_xi)
                #                         p3 = i (the subscript of yi)
                #               l = q1 + q2 (the row that yi is in),
                #                   where q1 = 1 + width (the row of ones, the rows of the input bits
                #                         q2 = i (the subscript of yi)
                matrix[1 + 2 * width + (i_of_xi - 1) * width + i][j] = matrix[i_of_xi][j] * matrix[1 + width + i][j]

    for i in range(1, width + 1):
        # apply multiply function to every row of the input bits, thus filling the rest of the matrix
        multiply(m, i)

    return m


def gt(row1, row2):
    """
        compare function used in the qsort function
        from left to right, if a[i] > b[i] then return True
        row1: the row to be compared, i.e. a
        row2: another row to be compared, i.e. b
    """
    return str([str(i) for i in row1]) > str([str(i) for i in row2])


def qsort(iterable, cmp):
    """
        a standard quicksort function
        iterable: an iterable object, which will be sorted
        cmp: a function that tells if an element is bigger than the other element
    """
    if not iterable:
        return []
    else:
        return qsort([x for x in iterable[1:] if cmp(x, iterable[0])], cmp) \
               + [iterable[0]] \
               + qsort([x for x in iterable[1:] if not cmp(x, iterable[0])], cmp)


def broaden_word(d):
    """
        prettify the debug information
    """
    return '{0:02d}'.format(d)


def gaussian_elimination_3(m):
    """
        gaussian-elimination for matrices over gf(2)
        m: matrix to operate with
    """
    MAT_COL = len(m[0])
    MAT_ROW = len(m)

    def find_first(col):
        """
            find the first row starting with 1 on the selected column,
            if none found, return -1
            col: the number of the selected column
        """
        for cnt, row in enumerate(m):
            if row[col] == 1:
                # test if there is another 1 in front of row[col]
                if 1 not in row[:col]:
                    info(CHANNEL_DBG, 'found eligible row %s:\t\t%s' % (broaden_word(cnt), row))
                    return cnt
        return -1


    for j in range(MAT_COL):
        info(CHANNEL_DBG, 'iterated to column %s -----------------------------------' % j)
        row_num = find_first(j)
        if row_num == -1:
            # no eligible row found for this column, moving on
            continue

        for i in range(row_num + 1, MAT_ROW):
            # apply the add function to the rows below row_num, whose jth element must be the first 1 in the row
            if m[i][j] == 1 and 1 not in m[i][:j]:
                info(CHANNEL_DBG, 'adding row %s to row %s:\t%s' % (broaden_word(row_num), broaden_word(i), m[i]))
                m[i].add(m[row_num], row_num)
                info(CHANNEL_DBG, 'row %s changed to:\t\t\t%s' % (broaden_word(i), m[i]))

        print_matrix(m)


if __name__ == '__main__':
    s = init_matrix(INPUT_WIDTH, SBOXS[INPUT_WIDTH])

    literals = get_monomials_literals(INPUT_WIDTH)

    for row in s:
        print row, ' + '.join([literals[i] for i in row.added_row])

    gaussian_elimination_3(s)

    s = qsort(s, gt)

    print_matrix(s)

    for row in s:
        print row, ' + '.join(sorted([literals[i] for i in row.added_row]))

